package arthur;

import java.util.Random;

public class quickSortRandomized {
		
	public int[] quickSort(int[]lista, int comeco, int finalDaLista) {
		if (comeco < finalDaLista){
			selectPivo(lista, comeco, finalDaLista);
			int aux = partition(lista, comeco, finalDaLista);
			
			quickSort(lista, comeco, aux - 1);
			quickSort(lista, aux + 1, finalDaLista);
		}
		return lista;
	}
	
	private void selectPivo(int[] lista, int comeco, int finalDaLista) {
		Random r1 = new Random();
		int variacao = ((finalDaLista - comeco) + 1);
		int posicaoPivo = r1.nextInt(variacao);
		posicaoPivo += comeco;
		swap(lista, finalDaLista, posicaoPivo);
	}
	
	private int partition(int[] lista, int comeco, int finalDaLista) {
		int pivo = lista[finalDaLista];
		int i = comeco - 1;
		
		for (int j = finalDaLista-1; j > i; j--) {
			if (lista[j] < pivo) {
				i++;
				swap(lista, j, i);
				j++;
			}
		}
		swap(lista, finalDaLista, i+1);
		return i+1;
	}
	
	private void swap(int[] lista, int a, int b) {
		int temp = lista[a];
		lista[a] = lista[b];
		lista[b] = temp;
	}
	

}
